package com.sicheng.lc.周赛.分类.位运算;

import java.util.HashSet;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/19 11:06
 */
public class 兼具大小写的最好英文字母 {
    //    https://leetcode.cn/problems/greatest-english-letter-in-upper-and-lower-case/
    public String greatestLetter(String s) {
        return bit(s);
    }

    //空间O(1) 时间O(n)
    //将出现的每一个字母压缩在一个64位的long变量,0表示出现，1表示未出现
    // 右移32位& 自己, 得到的2进制数的长度
    // dcba...HGFEDCBA
    // 1010...01011010  (字母出现的状态)
    //
    private String bit(String s) {
        long x = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            x |= 1L << s.charAt(i) - 'A';
        }
        x &= x >> 32;
        if (x == 0)
            return "";
        return String.valueOf((char) ('A' + Math.log(x) / Math.log(2)));

    }

    // 此算法 费空间 费时间 hash涉及函数调用开销
    private String getStringByHash(String s) {
        HashSet<Character> set = new HashSet<>();
        char best = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c <= 'Z') {
                if (set.contains((char) (c + 32))) {
                    best = (char) Math.max(best, c);
                }
            } else {
                if (set.contains((char) (c - 32))) {
                    best = (char) Math.max(best, c - 32);
                }
            }

            set.add(c);
        }

        if (best != 0)
            return String.valueOf(best);
        return "";
    }

    public static void main(String[] args) {
        兼具大小写的最好英文字母 solution = new 兼具大小写的最好英文字母();
        System.out.println(solution.bit("lEeTcOdE"));
    }
}
